package microsoft;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by lxy_920912 on 31/03/2017.
 */
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        this.val = x;
        this.left = null;
        this.right = null;
    }
    public TreeNode build(TreeNode root,int p,int q,int n){
        root.left = new TreeNode(p);
        root.right = new TreeNode(100-p);
        List<Float> result = new ArrayList<>();

        backBranch(root.left,p,q,n,1,1,result);
        backBranch(root.right,p,q,n,1,1,result);
        float x = 0;
        for(int i = 0;i < result.size();i++){
            x = result.get(i);
        }
        System.out.println(x);
        return  root;
    }
    public void backBranch(TreeNode root, int p, int q, int n, int lay, float expect, List<Float> result){

        expect = expect*((float)root.val/100);
        if(n <= 0){
            result.add(expect*lay);
        }
        if(n > 0){
            if(root.val >= 100){
                int val = p/2;
                root.left = new TreeNode(val);
                root.right = new TreeNode(100-val);

                backBranch(root.left,p,q,n-1,lay+1,expect,result);
                backBranch(root.right,p,q,n,lay+1,expect,result);
            }else{
                int val = root.val + q;
                if(val > 100){
                    root.left = new TreeNode(100);
                    backBranch(root.left,p,q,n-1,lay+1,expect,result);
                }else{
                    root.left = new TreeNode(val);
                    root.right = new TreeNode(100 - val);
                    backBranch(root.left,p,q,n-1,lay+1,expect,result);
                    backBranch(root.right,p,q,n,lay+1,expect,result);
                }
            }

        }


    }
}
